package com.arron.algorithm.leetcodetop100.数组;

import com.arron.algorithm.leetcodetop100.优先级队列.MaxPQ;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;


/**
 *  快排的应用
 */
public class 数组第k个最大元素 {


    public int findKthLargest_V3(int[] nums, int k) {

        //使用自定义实现的最大堆优先级队列

        MaxPQ maxPQ = new MaxPQ(nums.length);

        for (int i = 0; i < nums.length; i++) {
            maxPQ.insert(nums[i]);
        }

        while (k>1){

            System.out.println(maxPQ.delMax());
            k--;

        }

        return maxPQ.delMax();
    }


    public int findKthLargest(int[] nums, int k) {
        //使用最小堆
//        PriorityQueue<Integer> queue = new PriorityQueue<>();
        PriorityQueue<Integer> queue = new PriorityQueue<>(10,((o1, o2) -> o2-o1));
        for (int num : nums) {

            queue.offer(num);
        }

        for (int i = k; i> 1 ; i--) {
            System.out.println(queue.poll());
        }

        return queue.peek();
    }


    public int findKthLargestV2(int[] nums, int k) {
        return quickSort_v2(Arrays.stream(nums).boxed().collect(Collectors.toList()),k);
    }



    public Integer quickSort_v2(List<Integer> numsList, int k){


        int pivot = numsList.get(new Random().nextInt(numsList.size()));


        List<Integer> biggerList = new ArrayList<>();
        List<Integer> equalsList = new ArrayList<>();
        List<Integer> smallList = new ArrayList<>();

        for (Integer integer : numsList) {

            if (integer > pivot){
                biggerList.add(integer);
            }else if(integer < pivot){
                smallList.add(integer);
            }else {
                equalsList.add(integer);
            }

        }


        if ( k <=  biggerList.size()){
            return quickSort_v2(biggerList,k);
        }


        if ( k >equalsList.size()+biggerList.size()){

            return quickSort_v2(smallList,k-(equalsList.size()+biggerList.size()));
        }

        return pivot;
    }





    //单纯的快排
    public void quickSort(int[] nums){

        int left = 0;
        int right = nums.length-1;
        Collections.shuffle(Arrays.asList(nums));
        quickSort(nums,left,right);
    }



    public void quickSort(int[] nums,int left,int right){

        if (left>=right){
            return;
        }

        int  numIndex = sort(nums,left,right);

        System.out.println("numIndex : "+ numIndex+"  每轮的交换结果: "+Arrays.toString(nums));
       quickSort(nums, left, numIndex - 1);
       quickSort(nums, numIndex + 1, right);
    }

    private int sort(int[] nums, int left, int right) {


        int p1 = left+1;
        int p2 = right;
        while (p1 <=  p2){

            //在左边找到第一个大于 nums[root] 的元素
            while (p1 <= p2 && nums[p1] <= nums[left]){
                p1++;
            }

            //在右边区间找到第一个小于nums[root] 的元素
            while (p2 >= p1 && nums[p2] > nums[left]){
                p2--;
            }

            if (p1 > p2){
                swapNums(nums, left,p2);
                break;
            }

            if(p1 <p2){

                swapNums(nums,p1,p2);
            }

        }
        return p2;
    }

    private void swapNums(int[] nums, int p1, int p2) {

        int temp = nums[p1];
        nums[p1] = nums[p2];
        nums[p2] = temp;
    }

    public static void main(String[] args) {

        数组第k个最大元素 kk = new 数组第k个最大元素();
        int[] nums = {3,2,3,1,2,4,5,5,6};
        System.out.println("第k大元素 ： "+kk.findKthLargest(nums, 3));

    }

}
